

/*归并排序算法*/

void merger_sort(ElemType *arr,int arr_size)
{
	if(arr_size > 1)
	{
		ElemType *left_arr 	= arr;
		int left_size		= arr_size / 2;
		
		ElemType *right_arr	= arr + left_size;
		int right_size		= arr_size - left_size;
		
		merger_sort(left_arr,left_size);//递归
		merger_sort(right_arr,right_size);//递归
		
		merger_going(left_arr,left_size,right_arr,right_size);//递归
	}
}
	

/*归并操作*/

#define TEM_MAX_SIZE 20
void merger_going(ElemType *left_arr,int left_size,ElemType *right_arr,int right_size)
{
	int i_left = 0;
	int j_right = 0;
	int k_temp = 0;
	int m_for = 0;
	ElemType temp[TEM_MAX_SIZE];
	
	//比较左右序列中每一个元素得大小
	while(i_left < left_size && j_right < right_size)
	{
		if(left_arr[i_left] < right_arr[j_right])
		{
			temp[k_temp++] = left_arr[i_left++];
		}
		else
		{
			temp[k_temp++] = right_arr[j_right++];
		}
	}
	
	//处理左序列或右序列中最后一个元素
	while(i_left < left_size)
	{
		temp[k_temp++] = left_arr[i_left++];
	}
	while(j_right < right_size)
	{
		temp[k_temp++] = right_arr[j_right++];
	}
	
	//将temp中得元素都放到left_arr
	for(m_for = 0; m_for < (left_size + right_size); m_for++)
	{
		left_arr[m_for++] = temp[m_for++];
	}
	
}

